Data security has rapidly progressed from being an issue for only a few government and military entities to being a concern for almost everybody who uses or even deals with those who use a computer, “smart phone”, etc. “Security” can mean many things depending on the context. Just two of the very many examples are preventing others from accessing personal or otherwise confidential data, and detecting tampering. Sometimes, “security” means just being able to prove that some digital event happened or did not happen.
A common way to ensure data security is to have a trusted repository, with access controlled using such devices as passwords, digital certificates, encryption and keys, etc. In one sense, this simply removes the problem to a higher level, in that one must then trust the security procedures of the repository, the authority that issued the certificates and keys, etc. Moreover, the need for verifiability is increasing rapidly, with countless financial, business, technical, and other events being recorded in some way in remote storage such as in the “cloud”. With the advent of the “Internet of Things”, in which essentially everything that can pass data to a network may be communicating information for storage, central repositories and verification mechanisms are becoming more and more impractical.
One development that is showing promise as a way to register and verify information without reliance on centralized control is a decentralized data structure known as a “blockchain”. See FIG. 1. Although the term “blockchain” itself, as well as related terms, do not yet have universally accepted definitions, typically a “blockchain” 1000 is understood as being a data structure comprising a series of usually (but not necessarily) time-stamped blocks bi, . . . , bj-2, bj-1, bj, . . . , where each block includes not only submitted data, but also a  of all or some subset of the contents of the block, plus various metadata, hashed together with linking data, such as the hash output, of all or some sub-set of the data in an immediately preceding block. Thus, for example, block bj not only contains it own hash value j, but also a link from the previous block bj-1 based on its hash value j-1.
As FIG. 1 illustrates, data to be entered in the blockchain 1000 may be submitted as “transactions” by any of a set of client systems 100, via one or more communications channels such as networks, to one or more intermediate nodes 200, such as servers, which may also create transactions and comprise clients in their own right. The nodes 200 then typically aggregate one or more transactions into data blocks, and then some reconciliation mechanism 400 is applied to determine which blocks of which nodes are to be included in which order in the actual blockchain 1000, which may then be distributed (indicated by arrow 1100) or at least made accessible to the nodes 200.
Different reconciliation protocols have been suggested, the most common of which is the “proof of work” (PoW) arrangement used in the Bitcoin system. According to the PoW protocol, highest level ones of the nodes 200 act as “miners” who must solve a difficult computational problem; the first to solve it—which is easily verifiable by other nodes—is then allowed to enter the next block in the chain 1000. One known problem with the PoW arrangement is that it can have a settlement time on the order of many minutes, or at least many seconds, which leads to severe problems of scalability.
As another example, in some other systems, the various nodes “vote” and, according to some predetermined routine, come to a consensus as to which block is to be entered next into the blockchain 1000. Still other reconciliation protocols are known. One problem with such a voting protocol is that the set of voting nodes may change over time. One or more, for example, may become unavailable, no longer a member of the group, such that later confirmation of the “votes” may become difficult or, if reliant on currently unavailable and/or invalid keys, impossible. The network of servers established to enable verification of events recorded into blocks of the blockchain may therefore no longer be able to perform its intended function.
However it is established, the blockchain can then be used as, or as the basis of, a public ledger, which is typically an append-only database achieved by distributed consensus of multiple participants. Once data is entered into a block of the chain, the entry is essentially irrefutable, since any tampering with the data would be reflected in the chained hash calculations and thus easily detected.
As with other “real-life” transactions, users such as the clients 100 and/or the nodes 200 may want or need proof that a transaction was actually entered into the blockchain 1000. In other words, there is a need for an efficient way to provide blockchain receipts. One difficulty in this regard is that, for proper verification that a block exists in the blockchain, many existing blockchain systems require calculation along the chain from some known valid point and through every intermediate block. This is turn presupposes that all the intermediate blocks are stored and available, which typically precludes deletion of those blocks, for example, to save storage.